package day8;

public class code1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode a = headA;
        ListNode b = headB;

        while (a!=b){
            if (a==null){
                a = headB;
            }else {
                a = a.next;
            }
            if (b==null){
                b = headA;
            }else {
                b= b.next;
            }

        }

        return a;
    }


    public ListNode reverseList(ListNode head) {
        ListNode nh = new ListNode(0);
        while (head!=null){
            ListNode node = head.next;
            head.next = nh.next;
            nh.next = head;
            head = node;
        }

        return nh.next;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode a = head;
        ListNode b = head;
        while (b.next==null||b.next.next==null){
            a = a.next;
            b= b.next.next;
        }
        a = a.next;
        ListNode p = reverseList(a);
        b = head;
        while (p!=null){
            if(p.val!=b.val) return false;
            p = p.next;
            b = b.next;
        }
        reverseList(a);
        return true;

    }

    public boolean hasCycle(ListNode head) {
        ListNode a = head;
        ListNode b = head;
        if(a==null) return false;
        if(b.next==null||b.next.next==null) return false;
        a=a.next;
        b=b.next.next;
        while (b.next!=null&&b.next.next!=null){
            if(a.val==b.val) return true;
            a = a.next;
            b = b.next.next;
        }
        return false;

    }

    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode a = head;
        ListNode b = head;
        ListNode node = null;
        while (b.next!=null&&b.next.next!=null){
            a = a.next;
            b = b.next.next;
            if(a==b){
                node = a;
                break;
            }
        }
        if(node==null) return null;

        a = head;
        while (a!=node){
            a = a.next;
            node=node.next;
        }

        return node;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode node = new ListNode();
        ListNode n = node;

        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                ListNode ne = list1.next;
                list1.next = null;
                n.next = list1;
                n = n.next;
                list1 = ne;
            }else {
                ListNode ne = list2.next;
                list2.next = null;
                n.next = list2;
                n = n.next;
                list2 = ne;
            }
        }

        if(list1==null) n.next = list2;
        if(list2==null) n.next = list1;

        return node.next;
    }





}
